package leetcode.stack;

import java.util.HashMap;

public class TopKTimes {
    public static class Node{
        public String str;
        public int times;

        public Node(String str, int times) {
            this.str = str;
            this.times = times;
        }
    }
    public static class TopKRecord{
        private Node[] heap;
        private int index;
        private HashMap<String,Node> strNodeMap;
        private HashMap<Node,Integer> nodeIndexMap;

        public TopKRecord(int size){
            heap = new Node[size];
            index = 0;
            strNodeMap = new HashMap<String, Node>();
            nodeIndexMap = new HashMap<Node, Integer>();
        }
        public void add(String str){
            Node curNode =null;
            int preIndex =-1;
            if (!strNodeMap.containsKey(str)){
                curNode = new Node(str,1);
                strNodeMap.put(str,curNode);
                nodeIndexMap.put(curNode,-1);
            }else {
                curNode = strNodeMap.get(str);
                curNode.times++;
                preIndex = nodeIndexMap.get(curNode);
            }
            if (preIndex == -1){
                if (index == heap.length){
                    if (heap[0].times < curNode.times){
                        nodeIndexMap.put(heap[0],-1);
                        nodeIndexMap.put(curNode,0);
                        heap[0] = curNode;
                        heapify(0,index);
                    }else {
                        nodeIndexMap.put(curNode,index);
                        heap[index] = curNode;
                        heapInsert(index++);
                }
                }
            }else {
                heapify(preIndex,index);
            }
        }

        public void heapify(int index,int heapSize){
            int left = index*2+1;
            while (left<heapSize){
                int largest = left+1<heapSize && heap[left+1].times>heap[left].times?left+1:left;
                largest = heap[index].times> heap[largest].times?index:largest;
                if (largest == index){
                    break;
                }
                swap(index,largest);
                index = largest;
                left = index*2+1;
            }

        }
        public void heapInsert(int index){
            while (heap[index].times < heap[(index-1)/2].times){
                swap(index,(index-1)/2);
                index = (index-1)/2;
            }
        }
        public  void swap(int a,int b){
            int temp = heap[a].times;
            heap[a].times = heap[b].times;
            heap[b].times = temp;
        }


    }

    public static void main(String[] args) {
        TopKRecord topKRecord = new TopKRecord(3);
    }
}
